\section{Experiments}
\label{sec:exp}
In this section, we evaluate various team formation algorithms using the collaboration graph extracted from the DBLP bibliography server. We show that the density of the subgraph returned by our algorithms {\it s-DensestAlk} and {\it m-DensestAlk} perform favorably in comparison to the algorithm {\it MinDiameter}. We also show that our algorithm for density version provides high-quality results in terms of effective communication and collaboration (according to several metrics). In this section, we also present three simple heuristic extensions that can be used to process the solutions returned by {\it s-DensestAlk} and {\it m-DensestAlk} in order to further improve these solutions by reducing size and improving connectivity, while maintaining high density. 
%We demonstrate the effectiveness of these simple heuristic algorithms in order to achieve the solution that has high density, better connectivity and smaller cardinality.  
Finally, examples of teams reported by our methods qualitatively corroborate the effectiveness of our framework.
%illustrate the effectiveness of our framework in real scenarios. 

\subsection{Experimental Setup}
We use a snapshot of the DBLP data downloaded on May 17, 2010 to create a benchmark data set for our experiments. We only consider the papers published in the domains of Database (DB), Data Mining (DM), Artificial Intelligence (AI) and Theory (T) conferences. We select papers from a total of $21$ conferences categorized as follows: $DB = \{\textsc{sigmod, vldb, icde, icdt, edbt, pods}\} $, $DM = \{\textsc{www, kdd, sdm, pkdd, icdm}\}$, $AI =$ \{\textsc{icml, ecml,colt, uai}\}, and $T = \{\textsc{soda, focs, stoc, stacs, icalp, esa}\}$.
%We refer to the set of selected papers as the DBLP dataset. 
%We now proceed to generate the input to the Team Formation Problem as follows.
We define the skill set $\cal T = \{\textsc{t, ai, db, dm}\}$. The set of skilled individuals $X_{dblp}$ consists of the set of authors with at least three papers in these domains. Two authors $i_1, i_2$ are connected in the graph $G_{dblp} (X_{dblp}, E)$ if they appear as co-authors in at least two papers in DBLP. The above procedure creates a set $X_{dblp}$ consisting of $6137$ individuals. The maximum component size is $3869$. We use this for all the experiments. The skill set $X_i$ of each such author $i$ is defined as $X_i = \{ t \mid t \in {\cal T} \ and \ P_i(t) \ne \phi \}$ where $P_i(t)$ denotes the set of papers coauthored by $i$ that are published in the conferences in the domain $t$. 
%Further, each edge $e(i_1, i_2)$ is assigned an edge depending on the number of publications co-authored by $i_1$ and $i_2$.

%{\it Maximum Density Team Formation.} To evaluate the algorithms {\it s-DensestAlk} and {\it m-DensestAlk}, for each edge $e(i_1, i_2)$, we set the edge weight $w(i_1, i_2) = |P_{i1} \cap P_{i2}|$, where $P_{i1}$ and $P_{i2}$ represent the set of papers published by $i_1$ and $i_2$
{\it Maximum Density Team Formation.} To evaluate the algorithms ~\ref{algo:sDlk} and ~\ref{algo:mDlk}, for each edge $e(i_1, i_2)$, we set the edge weight $w(i_1, i_2) = |P_{i1} \cap P_{i2}|$, where $P_{i1}$ and $P_{i2}$ represent the set of papers published by $i_1$ and $i_2$ respectively. For the subgraph, say $G'(V', E')$ returned by these algorithms, we calculate the density, $d' = \frac{W(G')}{|V(G')|}$. 
% I COMMENTED THE BELOW. I GUESS ITS OK NOT TO TALK ABOUT THIS? - Atish
%Note that a different edge weight could also be chosen, such as $\frac{|P_{i1} \cap P_{i2}}{|P_{i1} \cup P_{i2}}|$. However, we wanted to associate higher weight with edges corresponding to {\em heavy} nodes. 
%Therefore we chose $|P_{i1} \cap P_{i2}|$.
%; as shown later, this does give us qualitatively good results.

{\it Minimum Diameter Team Formation.} Here, we set edge-weight $w(i_1, i_2) = 1 - \frac{|P_{i1} \cap P_{i2} |}{| P_{i1} \cup P_{i2} |}$ as suggested in the paper~\cite{LLT}.  For comparison, when a subgraph $G'(V', E')$ is returned by the {\it MinDiameter}, we compute its density by considering the induced subgraph on vertices $V''$, say $G''$ (which could contain more edges that $E'$). The density calculated is $d'' = \frac{W(G'')}{|V(G'')|}$ with edge weights $w(i_1, i_2) =  |P_{i1} \cap P_{i2}|$. 

%It is to be expected that {\it MinDiameter} performs worse in terms of density as the algorithm is designed to optimize a different objective. However, we believe that density is a better suited objective for collaborative compatibility. Further, the %goal of this section is to show that our density-based algorithms perform well independently. We therefore perform evaluations based on the objective as well as qualitatively. We now present the heuristic algorithms that build on algorithms {\it s-%DensestAlk} and {\it m-DensestAlk}.

\subsection{Heuristic algorithms}
\label{subsec:heuristic}
The objectives for {\it sTF-Density} and {\it mTF-Density} are to find subgraphs with maximum density satisfying the skill requirements. 
%such that it satisfies the skill-set requirement in order to perform the task $\cal T$. 
However, this does not necessitate a connected graph; disconnectedness makes meaningful collaboration in real-life difficult. This is an artifact of the objective function, rather than the algorithm. While the solutions returned by our algorithms {\it sTF-Density} and {\it mTF-Density} never had more than three components, we would like solutions with only one component. 
%This problem of disconnectivity is inherent due to the way we define the density of the graph and therefore, it is not really a problem introduced by poor algorithm. 
This is the motivation for heuristic improvements. A dual benefit in our suggested heuristics is that we are able to reduce the number of nodes in the returned subgraph.
% (while respecting the constraints of the task).
The hope is that these can be achieved without compromising significantly on the density.

%However, this serves as a motivation to think about the heuristics that can be applied to the solution in order to get a connected subgraph by sacrificing on the density a little. 
\begin{algorithm}[]
\caption{EnhanceComponent($G', T$)}
\label{algo:ecDlk} 
\begin{algorithmic}[1]
\STATE (Note: $T= \{<a, k>\}$)
\FOR {each component $C_i \in G'$}
\STATE $C'_i \leftarrow C_i$, $Ni \leftarrow N(C_i) - C_i$ 
\STATE (note: $N(C_i)$ denotes neighbors of nodes in $C_i$)
\FOR {each node $v \in N_i$}
\IF { $| V(C'_i) \cap S(a) | \ge k$}
\STATE ${\cal C'} \leftarrow {\cal C'} \cup C'_i$
\STATE break for loop
\ENDIF
\IF {$v \in S(a)$}
\STATE $C'_i \leftarrow C'_i \cup v $
\ENDIF
\ENDFOR
\ENDFOR
\end{algorithmic}
\end{algorithm}
\begin{algorithm}[]
\caption{EnhancedDense($G, T$)}
\label{algo:edDlk}
\begin{algorithmic}[1]
\STATE $G' \leftarrow$  {\it s-DensestAlk(G, T)}
\STATE ${\cal C'} \leftarrow {\it EnhanceComponent}(G', T)$
\STATE Return $\arg \min_{C'_i \in {\cal C'}} | C'_i |$ 
\end{algorithmic}
\end{algorithm}
We present three heuristics. The starting point of each is the solution to {\it sTF-Density} or {\it mTF-Density}, as the case may be.
We name these heuristics as {\it EnhancedDense} (Algorithm ~\ref{algo:edDlk}), {\it PartialTrimmedDense} (Algorithm ~\ref{algo:ptDlk})  and {\it CompleteTrimmedDense (Algorithm ~\ref{algo:ctDlk})}. For simplicity in presentation, the algorithms are presented as extensions to {\it s-DensestAlk}, but they apply to {\it m-DensestAlk} analogously. The basic idea behind algorithm {\it EnhancedDense} is to inspect each individual component in the solution and attempt to modify it so that it itself satisfies the skill set requirement imposed by the task $\cal T$. This is done by examining the neighbors of the nodes in the component and adding those neighbors that are skilled nodes. The heuristics {\it PartialTrimmedDense} and {\it CompleteTrimmedDense}, take as an input the components generated by the algorithm {\it EnhanceComponent} (Algorithm ~\ref{algo:ecDlk})  and attempt to reduce the size of each component by removing the non-skilled nodes one by one without making the component disconnected. The {\it PartialTrimmedDense}  algorithm allows at most $k$ non-skilled nodes in the component whereas {\it CompleteTrimmedDense} attempts to remove as many non-skilled nodes as possible. The smallest resulting component with the required skilled nodes is then picked. This helps reduce the size of the solution, which is now a single component, and hopefully still sufficiently dense since the heuristic started with a 3-approximation to the density objective. 
\begin{algorithm}[]
\caption{PartialTrimmedDense($G, T$)}
\label{algo:ptDlk}
\begin{algorithmic}[1]
\STATE (Note: $T = \{<a, k>\}$)
\STATE $G' \leftarrow$  {\it s-DensestAlk(G, T)}
\STATE ${\cal C'} \leftarrow {\it EnhanceComponent}(G',T)$
\FOR {each component $C'_i \in {\cal C'}$}
\STATE $Q \leftarrow \{ u \mid u \in C'_i \mbox { and } u \not \in S(a) \}$
\WHILE {$Q$ not empty and $| V(C'_i) - S(a) | > k$}
\STATE $u_{min} \leftarrow$ pop lowest degree node from $Q$
\IF {($C'_i - u_{min}$) is connected}
\STATE $C'_i \leftarrow C'_i - u_{min}$
\ENDIF
\ENDWHILE
\IF {$| V(C'_i) - S(a) | > k$}
\STATE ${\cal C'} \leftarrow {\cal C'} - C'_i$
\ENDIF
\ENDFOR 
\STATE Return $\arg \max_{C'_i \in {\cal C'}} density(C'_i)$ 
\end{algorithmic}
\end{algorithm}
\begin{algorithm}[]
\caption{CompleteTrimmedDense($G,T$)} 
\label{algo:ctDlk}
\begin{algorithmic}[1]
\STATE (Note: T $= \{<a, k>\}$)
\STATE $G' \leftarrow$  {\it s-DensestAlk(G,T)}
\STATE ${\cal C'} \leftarrow {\it EnhanceComponent}(G', T)$
\FOR {each component $C'_i \in {\cal C'}$}
\STATE $Q \leftarrow V(C_i) - S(a)$
\WHILE {$Q$ is not empty}
\STATE $u_{min} \leftarrow$ pop lowest degree node from $Q$
\IF {($C'_i - u_{min}$) is connected}
\STATE $C'_i \leftarrow C'_i - u_{min}$
\ENDIF
\ENDWHILE
\ENDFOR 
\STATE Return $\arg \min_{C'_i \in {\cal C'}} | V(C'_i) |$
\end{algorithmic}
\end{algorithm}

\subsection{Single Skill Team Formation}
We run the single skill experiments for $k \in \{3, 5, 7, 9, 11, 13, 15\}$. For each value of $k$, we have a separate run for each skill $a \in \{\textsc{t, ai, db, dm}\}$. 
%Therefore, for each value of $k$, we have four different solutions corresponding to four different skills. 
We calculate statistics, such as density, size, and number of connected components for each solution and present the mean over these four runs as the final statistic. 
%for the particular value of $k$. 

Figures~\ref{fig:kSingle}(a) and~\ref{fig:kSingle}(b) show ($k$ vs. density) and  ($k$ vs. size) plots, respectively. From these plots, we can see that the density obtained by {\it s-DensestAlk} significantly outperforms the density obtained by {\it MinDiameter} algorithm. This is of course expected. However, the downside is that the size of the solution to {\it s-DensestAlk} is also larger (and in some cases disconnected). 
%Although, this is expected because the objective of {\it MinDiameter} algorithm is to optimize  for minimum diameter and not for maximum density, these plots demonstrate that using our algorithm we have achieved the goal of finding a high density solution leading to a team with high collaborative compatibility. 
%However, like we mentioned earlier, the solution may  contain disconnected components. 
The heuristic {\it EnhancedDense} essentially adds neighbors to each component in the solution so that the resulting component satisfies the required skill-set and then picks the one with the smallest size. Therefore connectivity is guaranteed. Further, the reduction in density is not much and even the cardinality has reduced compared to the original solution. This also means that the solution returned by {\it s-DensestAlk} contained a good component to start with - by good component we mean a component that has most of the skills satisfied and has high density. 

\begin{figure*}[t]
\begin{center}
\subfigure[$k$ vs. density]{\includegraphics[angle=270, scale=0.20]{single_skill_k_density_3.eps}}
\subfigure[$k$ vs. size]{\includegraphics[angle=270, scale=0.20]{single_skill_k_size_3.eps}}
\subfigure[$k$ vs. density per node]{\includegraphics[angle=270, scale=0.20]{single_skill_k_density_per_node_3.eps}}
\caption{single skill experiments}\label{fig:kSingle}
\end{center}
\end{figure*}

Now, notice that by applying heuristics {\it PartialTrimmedDense} and {\it CompleteTrimmedDense}, we attempt to remove the non-skilled nodes one by one from each of these enhanced components (while maintaining connectivity). As the plots show again, this serves the purpose of significantly reducing the cardinality of the solution and as a hard constraint the algorithm still satisfies the skill requirement. 
%As a final solution, {\it PartialTrimmedDense} chooses a component with maximum density and has at most $k$ non-skilled nodes. Whereas {\it CompleteTrimmedDense} attempts to remove as many non-skilled nodes as possible and picks the one with maximum density. 
It can be observed from the plots that {\it PartialTrimmedDense} has density almost equal to the {\it s-DensestAlk} and the cardinality is reduced by more than fifty percent. Further, {\it CompleteTrimmedDense} gives a solution that has cardinality almost equal to $k$ (which would be optimal), with very little reduction in density. Finally, we plot ($k$ vs. density per node) in Figure~\ref{fig:kSingle}(c). While this figure can be deduced, we present it to highlight the observation that the heuristics reduce the cardinality without compromising on the density. Notice that in this plot, {\it CompleteTrimmedDense} has the highest value of density per node, for every value of $k$. 

Given that density is intuitively a better measure of team collaboration, these results show that we are completely able to eliminate connectivity issues inherent in this objective, and output small yet sufficient, and highly collaborative (dense) teams. %We now show similar experiments for multiple skill team formation.

%This implies that using these heuristic, we have completely overcome the problem of connectivity in the sense that the solution always consists of a single component and in each of these heuristics, the density is compromised by a very low factor and the cardinality is also much lower.  

\subsection{Multiple Skill Team Formation}
We run the multiple skill experiments for $k \in \{3, 8, 13, 18, 23, 28 \}$ and for each run, we randomly choose $k$ skills from $\cal A = \{ \textsc{t, ai, db, dm} \}$. For example, when $k=3$, we may choose a skill (multi)set \textsc{\{t, t, dm\}} which means we want a subgraph that contains at least two authors of skill $T$ and one author of skill $DM$. Recall that a given author can have multiple skills and therefore the solution may consist of a subgraph whose size is less than the value of $k$. 
%Here again, we compare the solution returned by {\it maximum-density} and {\it minimum-diameter} algorithms with respect to the properties such as density, size and number of connected components. 

\begin{figure}[h]
\begin{center}
\subfigure[$k$ vs. density]{\includegraphics[angle=270, scale=0.2]{multi_skill_k_density_int_3.eps}}
\subfigure[$k$ vs. size]{\includegraphics[angle=270, scale=0.2]{multi_skill_k_size_int_3.eps}}
\caption{multiple skills experiments}\label{fig:kMulti}
\end{center}
\end{figure}

Figures~\ref{fig:kMulti}(a) and~\ref{fig:kMulti}(b) plots ($k$ vs. density) and  ($k$ vs. size), respectively, for multiple skill team formation experiments. 
Note that the plots for multiple skill experiments fluctuate more than single skill experiments. This is due to the randomness in picking the multiple skills requirements. Also, some solutions returned are of the same size even as $k$ is increased. This is because sometimes the same solution satisfies different required skill sets.

In these figures, we again see that {\it m-DensestAlk} algorithm has the highest density.
%outperforms the density obtained by {\it MultipleSkillMinDiameter} algorithm and we form a team with many opportunities for effective collaboration. 
Note that the solution with density $0$ and size $1$ corresponds to an individual that has all the required skills. 
%to perform the task $\cal T$ and therefore, it does not necessarily imply a bad solution as far as maximum-density objective is concerned.  
Further, similar to single skill experiments, we apply the heuristics mentioned earlier in order to get a connected subgraph without compromising on the density much.  Figure~\ref{fig:kMulti}(b) shows that the heuristics have been effective in reducing cardinality. In fact, the cardinality of the solution obtained by {\it CompleteTrimmedDense} is lesser than $k$ because a single individual can satisfy more than one skills. Further, for the $k\geq 13$ tasks, the density achieved by the heuristics is also close to that of {\it m-DensestAlk}. While sometimes certain heuristics have low density (e.g., $k=3$ or $k=8$), all heuristics offer a nice trade-off between size and density (and return connected solutions by design). For each value of $k$, there exists at least one solution with density close to maximum-density and small cardinality. We omit the density per node plot here due to lack of space, and because it can be deduced from Figures~\ref{fig:kMulti}(a), (b).

%Also note that for these experiments, the skills were chosen randomly and we happened to get the same solution that satisfy the multiple skills corresponding to different values of $k$ and therefore, we see the same values for size and density even if the value of $k$ increases. Also, owing to the randomness of the skills chosen and since some skills are more common than the rest, the size and therefore density of the enhanced and trimmed components may also fluctuate and not necessarily have a strong correlation with the increasing value of $k$. 

\subsection{Density Vs. Diameter Analysis}
In the previous sections, we demonstrated the effectiveness of various heuristic algorithms in order to obtain a solution subgraph that is connected, small and dense. The intuition behind suggesting the density as a metric for team collaborative compatibility is that a denser graph has more edges between nodes, resulting in a greater possibility for collaboration. Small diameter does not necessarily guarantee this property. In this section, we consider three metrics for comparing Density and Diameter based approaches: {\it teamPubs, partialTeamPubs}  and {\it teamPubRatio}. The metric {\it teamPubs} defines the number of publications where all the authors of the publication belong to the solution subgraph. {\it partialTeamPubs} defines the number of publications where at least half of the authors of the publication belong to the solution subgraph. These two metrics give a good indication of the collaboration compatibility of reported teams. In addition, we propose another metric {\it teamPubRatio} which is essential for the comparative study because it is affected by not only the team-members' collaboration compatibility but also on the size of the team. In this case, for each publication, say $p'$, we compute the ratio of $\frac{\mid X' \cap A' \mid}{\mid X' \cup A' \mid}$ where $X'$ is the set of authors in the solution subgraph and $A'$ is the set of authors of the publication $p'$. That is, {\it teamPubRatio} measures the Jaccard similarity between a publication's author set and a team's author set. We then take the average of this quantity over all the publications. 
%This {\it teamPubRatio} metric helps us distinguish between the effectiveness of the teams of varying sizes. 

We now describe the details of the evaluation strategy used to calculate these metrics. For both single skill team formation and multiple skill team formation problems, we consider the teams that were proposed as a solution in the previously described experiments. In particular, we consider the solutions reported by the algorithms {\it CompleteTrimmedDense} and {\it MinDiameter}. We choose only {\it CompleteTrimmed-Dense} algorithm for density because it reports the smallest solutions. The goal is to establish that the small teams obtained by {\it CompleteTrimmedDense} also achieve superior results for the three metrics of collaboration compatibility mentioned above. The results of metric evaluation are shown in the plots ~\ref{fig:kDensityVsDiaSingleSkill} and ~\ref{fig:kDensityVsDiaMultiSkill} for single skill and multi skill experiments, respectively. In each plot, value of $k$ is plotted along the $x$-axis and the value of the the metrics for the corresponding solution subgraphs are along the $y$-axis. In case of single skill experiments, for each $k$, the metric value reported is the average of metric values for the solutions corresponding to each of the skills  $\{$ \textsc {t, ai, db, dm}  $\}$. Further, for the metrics {\it teamPubs} and {\it partialTeamPubs} the $y$-axis defines the resulting number of publications whereas for the metric {\it teamPubRatio}, the $y$-axis defines the {\it scaled} ($100000$ times) metric value. From these plots it can be observed that in both single skill and multi skill team formation problems, the algorithm {\it CompleteTrimmedDense} consistently outperforms the algorithm {\it MinDiameter} for all the three metrics. In case of single skill, for each of the three metrics, and for most values of $k$, the metric value for {\it CompleteTrimmedDense} is about twice that of {\it MinDiameter}. In multi skill, the variation is somewhat larger, but {\it CompleteTrimmedDense} consistently displays superior metric values for all cases. Recall that the size of the solution teams by both these algorithms were very similar (and the metric {\it teamPubRatio} does not necessarily benefit with larger team size); therefore, these experiments suggest that density-based team formation leads to teams with better collaborative compatibility than the diameter-based team formation.
\begin{figure*}[h]
\begin{center}
\subfigure[k vs.Number of Publications]{\includegraphics[angle=270, scale=0.30]{SingleSkillMetricsNumPubs.eps}}
\subfigure[k vs. Jaccard Distance]{\includegraphics[angle=270, scale=0.30]{SingleSkillMetricsPubRatio.eps}}
\caption{Single Skill Density vs. Diameter Analysis}\label{fig:kDensityVsDiaSingleSkill}
\end{center}
\end{figure*}
\begin{figure*}[h]
\begin{center}
\subfigure[k vs. Number of Publications]{\includegraphics[angle=270, scale=0.30]{MultiSkillMetricsNumPubs.eps}}
\subfigure[k vs. Jaccard Distance]{\includegraphics[angle=270, scale=0.30]{MultiSkillMetricsPubRatio.eps}}
\caption{Multiple Skill Density vs. Diameter Analysis}\label{fig:kDensityVsDiaMultiSkill}
\end{center}
\end{figure*}
%\begin{figure*}[h]
%\begin{center}
%\subfigure[Single Skill Metric Evaluation]{\includegraphics[angle=270, scale=0.30]{SingleSkillMetrics.eps}}
%\subfigure[Multiple Skill Metric Evaluation]{\includegraphics[angle=270, scale=0.30]{MultiSkillMetrics.eps}}
%\caption{Density vs. Diameter Analysis}\label{fig:kDensityVsDia}
%\end{center}
%\end{figure*}
\subsection{Qualitative evidence}
To analyze the quality of teams that are returned by our algorithms for maximum density, we refer to the {\it Most Cited Computer Science Authors} list maintained by {\it CiteSeerX} (citeseerx.ist.psu.edu/stats/authors?all=true) which contains most cited $10000$ authors. We also refer to the list {\it Central Authors: Computer Science (all-time)} published at (confsearch.org/confsearch/ca.jsp)~\cite{KW}. This list contains $1000$ researchers ranked on the basis of DBLP publications.

We examine the authors of teams returned by {\it s-DensestAlk} and {\it m-DensestAlk} algorithms in order to determine how many authors in the team are among top $500$ and top $1000$ most cited authors according to the list maintained by {\it CiteSeerX}. Due to space constraints, we present only some representative lists from single skill team formation in Table~\ref{QualityAnalysis}. The lists are for $k=3$ for $T$ and $DB$, and for $k=15$ for $DM$ and $AI$.
%gives examples of some of the experiments that we conducted. In particular, first eight rows in the table contain results of single skill team formation problem for each of the skills in ${\cal A} = \{ T, AI, DB, DM \}$ and for $k = \{ 3, 15 \}$. The last two rows contain the information about the teams formed for multiple skill team formation problem for $k = \{ 3, 28 \}$. We chose these values of $k$ because, they denote the minimum and maximum values of $k$ for which we have run the various sets of single and multiple skill team formation experiments. Further, in the table ~\ref{QualityAnalysis}, 
Team members who appear among the top $500$ and $1000$ cited authors are indicated by bold and italic font, respectively.
We can see from these results that in each team, we have many top cited and prolific/famous authors (who may not be in the top $1000$ list). These results show that teams formed by choosing the objective of maximum density subgraph are {\em intuitively} meaningful. 

\begin{table*} [t]
\caption{Teams reported by s-DensestAlk.}
%\caption{Teams reported by s-DensestAlk and m-DensestAlk. Column $1$ indicates the skill requirement and column $2$ specifies the authors that form the corresponding teams.}
\label{QualityAnalysis}
\begin{tabular}{lll}
Skills&Authors\\
\hline
T(3)&{\bf Prabhakar Raghavan, Ravi Kumar, Philip S. Yu}, D. Sivakumar, Sridhar Rajagopalan,\\
&Andrew Tomkins \\
DB(3)&{\bf Philip S. Yu,  Haixun Wang, Jiawei Han}, Xifeng Yan, Wei Fan, Hong Cheng,\\
&Charu C. Aggarwal\\
DM(15)&{\bf Jiawei Han, Zheng Chen, Haixun Wang, Philip S. Yu }, Amr El Abbadi,\\
&Benyu Zhang,Wei Fan, Jun Yan, Shuicheng Yan, Hong Cheng, Qiang Yang, Ning Liu, \\
&Jian Pei, Charu C. Aggarwal, Xifeng Yan, Divyakant Agrawal\\
AI(15)&{\bf Ravi Kumar, Ronald Fagin, Philip S. Yu,  Christos Faloutsos,  Zheng Chen},\\
& {\it Wei-Ying Ma, Andrei Z. Broder, Jian-Tao Sun, Hongjun Lu}, Dou Shen,Shuicheng Yan,\\
&Anthony K. H. Tung, Wei Fan, Sridhar Rajagopalan, Qiang Yang, Eli Upfal,\\
&Andrew Tomkins, Jure Leskovec
\end{tabular}
\end{table*}

Complementary results are seen on using the second list, i.e. a list of top $1000$ ranked researchers~\cite{KW}. Instead of presenting another table with author names corresponding to this list, we adopt a different approach for measuring quality. We determine the overall rank of a team using the ranks of the individual authors within the team. To be specific, we compute the mean reciprocal rank of all the skilled individuals in the team and report the final rank of the team as $r = 1000 \frac{\sum_{i}\frac{1}{r_i}}{n_s}$ where $r_i$ denotes the rank of a skilled individual and $n_s$ denotes the skilled individuals in the team. Similar findings are observed if this quantity includes non-skilled nodes as well.
%Further, we do consider the ranks of only skilled individuals in the team because our primary interest is to find a team that satisfies the given skill-set requirements. 
We report the ranks observed in Table~\ref{RankAnalysis}. Our original algorithms for maximum density and the subsequent heuristics form a team of highly ranked authors and perform significantly better than the minimum-diameter algorithm.
The validation of these algorithms over two different qualitative approaches provides further credence to this framework of team formation using a density based objective.

\begin{table}[t]
\caption{Team ranks based on top-ranked authors.}
%reported by \{s/m\}-DensityAlk, CompleteTrimmedDense, and Minimum-Diameter algorithms.}
\label{RankAnalysis}
\begin{tabular}{llll}
Skills&\{s/m\}-&CompleteTrimmed&Min\\
&DensityAlk&Dense&Diameter\\
\hline
T(3)&23.42&8.11&0\\
AI(3)&20.81&17.34&0\\
DB(3)&18.25&18.25&0\\
DM(3)&18.25&18.25&0\\
T(15)&14.95&19.67&2.05\\
AI(15)&15.25&14.48&1.86\\
DB(15)&10.54&10.80&0.75\\
DM(15)&9.55&9.93&1.05\\
T(1),DB(1),&18.25&100&24.39\\
DM(1)&&&\\
T(8),AI(6),&9.49&6.3&4.1\\
DB(8),DM(6)&&&\\
\end{tabular}
\end{table}

